/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Hua YY
 * Date: 2025-02-16
 * Time: 22:56
 */
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    //画个图就清晰多了，奇数个节点和偶数个节点
    public boolean isPalindrome(ListNode head) {
        ListNode mid = midNode(head);
        ListNode reverseHead = reverseList2(mid);
        //没有断
        while(reverseHead != null){
            if(head.val != reverseHead.val){
                return false;
            }
            head = head.next;
            reverseHead = reverseHead.next;
        }
        return true;
    }

    public ListNode midNode(ListNode head){
        //快慢双指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    public ListNode reverseList(ListNode head){
        //new 虚拟null节点
        ListNode pre = null;
        ListNode cur = head;
        //头插
        while(cur != null){
            ListNode tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

    public ListNode reverseList2(ListNode head){
        //递归的方法，head等不等于null，就是以防给的是空链表
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = reverseList(head.next);//新的头结点
        head.next.next = head;
        head.next = null;
        return newHead;

    }

}
public class Test7 {
}
